package com.xufx.algorithm.doublepointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * leetcode 15. 3sum
 * @link https://leetcode.cn/problems/3sum/description/
 * describe: Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
 *
 * Notice that the solution set must not contain duplicate triplets.
 *
 * example:
 * Input: nums = [-1,0,1,2,-1,-4]
 * Output: [[-1,-1,2],[-1,0,1]]
 * Explanation:
 * nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
 * nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
 * nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
 * The distinct triplets are [-1,0,1] and [-1,-1,2].
 * Notice that the order of the output and the order of the triplets does not matter.
 *
 * NOTICE: 此题有两个值得注意的地方
 *  1. 利用双指针减少时间复杂度
 *  2. 对于去重的部分，一定要是这一次和上一次比。
 *      比如，
 *      第一层循环，i和i - 1比；
 *      左指针，left 和left - 1比；
 *      右指针，right和right + 1比
 *
 */
public class Leetcode15ThreeSum {
    public static void main(String[] args) {
        // Example
        int[] nums = new int[]{-1, 0, 1, 2, -1, -4};
        List<List<Integer>> res = threeSum(nums);
        System.out.println(res);
    }

    private static List<List<Integer>> threeSum(int[] nums) {
        List res = new ArrayList();
        Arrays.sort(nums);
        // 利用双指针减少时间复杂度
        int len = nums.length;
        for (int i = 0; i < len; i++){
            // 和上一个循环的i比较，如果一样，则继续往下
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            int left = i + 1;
            int right = len - 1;

            while(left < right){
                // 循环中先处理重复情况
                if(left > i + 1 && nums[left] == nums[left - 1]){
                    left ++;
                    continue;
                }

                if(right < len - 1 && nums[right] == nums[right + 1]){
                    right--;
                    continue;
                }
                if(nums[i] + nums[left] + nums[right] == 0){
                    List<Integer> temRes = new ArrayList();
                    temRes.add(nums[i]);
                    temRes.add(nums[left]);
                    temRes.add(nums[right]);
                    res.add(temRes);
                    left++;
                }else if(nums[i] + nums[left] + nums[right] > 0){
                    right--;
                }else{
                    left++;
                }
            }
        }
        return res;
    }
}
